home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / Dylan Related / Mindy / Mindy 1.2 - portable sources / libraries / dylan / deque.dylan < prev    next >
Encoding:
Text File  |  1995-03-15  |  27.0 KB  |  813 lines  |  [TEXT/ttxt]
  1. module: Dylan
  2. author: David Pierce (dpierce@cs.cmu.edu)
  3. rcs-header: $Header: deque.dylan,v 1.11 94/11/03 23:50:57 wlott Exp $
  4.  
  5. //======================================================================
  6. //
  7. // Copyright (c) 1994  Carnegie Mellon University
  8. // All rights reserved.
  9. // 
  10. // Use and copying of this software and preparation of derivative
  11. // works based on this software are permitted, including commercial
  12. // use, provided that the following conditions are observed:
  13. // 
  14. // 1. This copyright notice must be retained in full on any copies
  15. //    and on appropriate parts of any derivative works.
  16. // 2. Documentation (paper or online) accompanying any system that
  17. //    incorporates this software, or any part of it, must acknowledge
  18. //    the contribution of the Gwydion Project at Carnegie Mellon
  19. //    University.
  20. // 
  21. // This software is made available "as is".  Neither the authors nor
  22. // Carnegie Mellon University make any warranty about the software,
  23. // its performance, or its conformity to any specification.
  24. // 
  25. // Bug reports, questions, comments, and suggestions should be sent by
  26. // E-mail to the Internet address "gwydion-bugs@cs.cmu.edu".
  27. //
  28. //======================================================================
  29. //
  30. // This file contains definitions of classes and functions for the Dylan
  31. // deque collection class.  The data structure used for deque is a
  32. // doubly-linked list of element objects.  Element objects each contain a
  33. // piece of data and previous and next element pointers.
  34. //
  35. // Written by David Pierce
  36. //  Translated to infix by Robert Stockton
  37. //
  38.  
  39.  
  40.  
  41. //; Dylan Deque Class Definition
  42.  
  43. // The <deque> class defines double ended queues.  A deque allows accesses
  44. // from both ends of the queue.  Used with PUSH and POP, a deque may be
  45. // treated as a stack.  When PUSH-LAST and POP-LAST are used, more
  46. // complicated things can be done.  And the regular sequence and
  47. // collection operations allow one to work with the deque as a whole.
  48. // This implementation of deques uses element objects with pointers to
  49. // represent the deque.
  50.  
  51. // <deque-element> -- internal
  52. //
  53. // Each <deque-element> has a DEQUE-ELEMENT-DATA slot and slots for the
  54. // prvious and next deque elements.  If there is no PREV-DEQUE-ELEMENT or
  55. // NEXT-DEQUE-ELEMENT, the marker #f should be used in these slots.
  56. //
  57. define class <deque-element> (<object>)
  58.     slot deque-element-data, init-keyword: data: ;
  59.   slot prev-deque-element, init-value: #f;
  60.   slot next-deque-element, init-value: #f;
  61. end class <deque-element>;
  62.  
  63. // Note: When union types make it into Dylan, if it's possible we will
  64. // want to type the previous and next slots of deque-elements.
  65.  
  66. // <deque> -- public
  67. //
  68. // Deque objects have slots for the head and tail of the queue.  The
  69. // DEQUE-HEAD and DEQUE-TAIL of a deque must always be instances of
  70. // <deque-element>; except when the deque is empty, in which case
  71. // DEQUE-HEAD and DEQUE-TAIL must both be #f.  This invariant must always
  72. // be preserved by the deque functions.
  73. //
  74. define class <deque> (<stretchy-collection>, <mutable-sequence>)
  75.   slot size :: <fixed-integer>,
  76.     setter: deque-size-setter,
  77.     init-value: 0,
  78.     init-keyword: size: ;
  79.   slot deque-head, init-value: #f;
  80.   slot deque-tail, init-value: #f;
  81. end class <deque>;
  82.  
  83. // Note: When union types make it into Dylan we will want to use these
  84. // here to type the DEQUE-HEAD and DEQUE-TAIL.
  85.  
  86. // Note: In the code that follows, the terms "state" and "element" will be
  87. // used interchangeably to denote <deque-element> objects.  The choice of
  88. // term used will usually depend on the context.  If the object is used as
  89. // a pointer into the deque structure, the term "state" will probably be
  90. // used.  If it is used as containing a piece of deque data, the term
  91. // "element" may be used.
  92.  
  93. // Deque operations -- public
  94. //
  95. // These are the main functions to use with deques.
  96. //
  97. define generic push (deque, new);
  98. define generic pop (deque);
  99. define generic push-last (deque, new);
  100. define generic pop-last (deque);
  101.  
  102. // $deque-fill-default$ -- internal
  103. //
  104. // Default fill value for new deque elements.
  105. //
  106. define constant $deque-fill-default$ = #f;
  107.  
  108. // initialize -- interface
  109. //
  110. // This initialize method implements the keys specified for deques.  The
  111. // SIZE key indicates the number of elements the deque should initially
  112. // have, and the FILL key indicates what the values of these initial
  113. // elements should be.  I added another key DATA which gives the entire
  114. // contents to the new deque in a sequence.
  115. //
  116. define method initialize (deque :: <deque>,
  117.               #key data, size = 0, fill = $deque-fill-default$)
  118. //  deque.deque-head := #f;
  119. //  deque.deque-tail := #f;
  120.   deque.deque-size := size;
  121.   if (data)
  122.     for (element in data)
  123.       push-last(deque, element);
  124.     end for;
  125.   else
  126.     for (s from 0 below size)
  127.       push-last(deque, fill);
  128.     end for;
  129.   end if;
  130. end method initialize;
  131.  
  132. // I don't understand why I have to set DEQUE-HEAD and DEQUE-TAIL to #f.
  133. // They should already be initialized by the INIT-VALUE: key I gave when I
  134. // created the class!
  135.  
  136.  
  137.  
  138. //; Iteration Protocol
  139.  
  140. // States in the iteration protocol are deque-elements from the deque that
  141. // you are working with.  The initial state is the first deque element and
  142. // the final state is the last deque element.  The next state is found by
  143. // looking at the NEXT-DEQUE-ELEMENT slot in the deque-element.  The
  144. // current element is the data found in the DEQUE-ELEMENT-DATA slot of the
  145. // deque-element.
  146.  
  147. define constant deque_fip_next_state =
  148.   method (deque :: <deque>, state :: <deque-element>) => <object>;
  149.     next-deque-element(state);
  150.   end method;
  151.  
  152. define constant deque_fip_prev_state =
  153.   method (deque :: <deque>, state :: <deque-element>) => <object>;
  154.     prev-deque-element(state);
  155.   end method;
  156.  
  157. define constant deque_fip_finished_state? =
  158.   method (deque :: <deque>, state, limit) => <object>;
  159.     ~state;
  160.   end method;
  161.  
  162. define constant deque_fip_current_key =
  163.   method (deque :: <deque>, state :: <deque-element>) => <fixed-integer>;
  164.     for (count from -1,
  165.      deque_elem = state then prev-deque-element(deque_elem),
  166.      while deque_elem)
  167.     finally
  168.       count;
  169.     end for;
  170.   end method;
  171.  
  172. define constant deque_fip_current_element =
  173.   method (deque :: <deque>, state :: <deque-element>) => <object>;
  174.     deque-element-data(state);
  175.   end method;
  176.   
  177. define constant deque_fip_current_element-setter =
  178.   method (value, deque :: <deque>, state :: <deque-element>) => <object>;
  179.     deque-element-data(state) := value;
  180.   end method;
  181.   
  182. define constant deque_fip_copy_state =
  183.   method (deque :: <deque>, state :: <deque-element>) => <deque-element>;
  184.     state;
  185.   end method;
  186.   
  187. define method forward-iteration-protocol (deque :: <deque>)
  188.   values(deque-head(deque), #f, deque_fip_next_state,
  189.      deque_fip_finished_state?, deque_fip_current_key,
  190.      deque_fip_current_element, deque_fip_current_element-setter,
  191.      deque_fip_copy_state);
  192. end method forward-iteration-protocol;
  193.  
  194. define method backward-iteration-protocol (deque :: <deque>)
  195.   values(deque-tail(deque), #f, deque_fip_prev_state,
  196.      deque_fip_finished_state?, deque_fip_current_key,
  197.      deque_fip_current_element, deque_fip_current_element-setter,
  198.      deque_fip_copy_state);
  199. end method backward-iteration-protocol;
  200.  
  201. // drop! -- internal
  202. //
  203. // DROP! is a nice utility function that is used in the functions below.
  204. // It works with a current deque-element in the deque.  DROP! splices the
  205. // deque-element before and after the given element so that the given
  206. // element is no longer attached to the deque.  In the special case that
  207. // the element is the head or tail (or both in the case of one element
  208. // deque) DROP! adjusts DEQUE-HEAD or DEQUE-TAIL.
  209. //
  210. define method drop! (deque :: <deque>, element :: <deque-element>)
  211.   case
  212.     element == deque-head(deque) & element == deque-tail(deque) =>
  213.       // Zero or one elements in deque
  214.       deque-head(deque) := #f;
  215.       deque-tail(deque) := #f;
  216.     element == deque-head(deque) =>
  217.       // ELEMENT is the head of the deque
  218.       deque-head(deque) := next-deque-element(element);
  219.       prev-deque-element(deque-head(deque)) := #f;
  220.     element == deque-tail(deque) =>
  221.       // ELEMENT is the tail of the deque
  222.       deque-tail(deque) := prev-deque-element(element);
  223.       next-deque-element(deque-tail(deque)) := #f;
  224.     otherwise =>
  225.       // ELEMENT is a normal element in the middle of the deque
  226.       next-deque-element(prev-deque-element(element)) :=
  227.         next-deque-element(element);
  228.       prev-deque-element(next-deque-element(element)) :=
  229.      prev-deque-element(element);
  230.   end case;
  231.   deque.deque-size := size(deque) - 1;
  232.   deque;
  233. end method drop!;
  234.  
  235.  
  236. //; Deque Functions
  237.  
  238. // push -- public
  239. //
  240. // Creates a new deque-element with data new and places it at the
  241. // DEQUE-HEAD of the deque.  If the deque is empty, both DEQUE-HEAD and
  242. // DEQUE-TAIL must be set to the new element.
  243. //
  244. define method push (deque :: <deque>, new)
  245.   let new-element = make(<deque-element>, data: new);
  246.   case
  247.     empty?(deque) =>
  248.       deque-head(deque) := new-element;
  249.       deque-tail(deque) := new-element;
  250.     otherwise =>
  251.       next-deque-element(new-element) := deque-head(deque);
  252.       prev-deque-element(deque-head(deque)) := new-element;
  253.       deque-head(deque) := new-element;
  254.   end case;
  255.   deque.deque-size := size(deque) + 1;
  256.   deque;
  257. end method push;
  258.  
  259. // pop -- public
  260. //
  261. // Removes the first deque-element and returns its DEQUE-ELEMENT-DATA.  If
  262. // the deque is empty, an error is signalled.
  263. //
  264. define method pop (deque :: <deque>)
  265.   case
  266.     empty?(deque) =>
  267.       error("POP:  deque empty.");
  268.     deque-head(deque) == deque-tail(deque) =>
  269.       let first-element = deque-head(deque);
  270.       deque.deque-size := 0;
  271.       deque-head(deque) := #f;
  272.       deque-tail(deque) := #f;
  273.       deque-element-data(first-element);
  274.     otherwise =>
  275.       let first-element = deque-head(deque);
  276.       deque.deque-size := size(deque) - 1;
  277.       deque-head(deque) := next-deque-element(first-element);
  278.       prev-deque-element(deque-head(deque)) := #f;
  279.       deque-element-data(first-element);
  280.   end case;
  281. end method pop;
  282.  
  283. // push-last -- public
  284. //
  285. // Creates a new deque-element and places it at the DEQUE-TAIL of the
  286. // deque.
  287. //
  288. define method push-last (deque :: <deque>, new)
  289.   let new-element = make(<deque-element>, data: new);
  290.   case
  291.     empty?(deque) =>
  292.       deque-head(deque) := new-element;
  293.       deque-tail(deque) := new-element;
  294.     otherwise =>
  295.       prev-deque-element(new-element) := deque-tail(deque);
  296.       next-deque-element(deque-tail(deque)) := new-element;
  297.       deque-tail(deque) := new-element;
  298.   end case;
  299.   deque.deque-size := size(deque) + 1;
  300.   deque;
  301. end method push-last;
  302.  
  303. // pop-last -- public
  304. //
  305. // Removes the last deque-element and returns its DEQUE-ELEMENT-DATA.
  306. //
  307. define method pop-last (deque :: <deque>)
  308.   case
  309.     empty?(deque) =>
  310.       error("POP-LAST:  deque empty.");
  311.     deque-head(deque) == deque-tail(deque) =>
  312.       let last-element = deque-tail(deque);
  313.       deque.deque-size := 0;
  314.       deque-head(deque) := #f;
  315.       deque-tail(deque) := #f;
  316.       deque-element-data(last-element);
  317.     otherwise =>
  318.       let last-element = deque-tail(deque);
  319.       deque.deque-size := size(deque) - 1;
  320.       deque-tail(deque) := prev-deque-element(last-element);
  321.       next-deque-element(deque-tail(deque)) := #f;
  322.       deque-element-data(last-element);
  323.   end case;
  324. end method pop-last;
  325.  
  326.  
  327.  
  328. //; Collection Function Methods
  329.  
  330. // Most of the methods for functions on general collections have been left
  331. // as the default.  This works well because these functions are
  332. // implemented primarily in terms of the iteration protocol.
  333. //
  334. // The collection functions that must be implemented (besides the
  335. // iteration protocol functions) are CLASS-FOR-COPY and MAP-AS.
  336. // Definitions for these are below.
  337.  
  338. // class-for-copy -- public
  339. //
  340. // Return the class for copy of deques (<deque>).
  341. //
  342. define method class-for-copy (deque :: <deque>)
  343.   <deque>;
  344. end method class-for-copy;
  345.  
  346. // size-setter -- public
  347. //
  348. // If N is larger than the size of the deque, extra copies of
  349. // $DEQUE-FILL-DEFAULT$ are pushed to the end until the size is N.  If N
  350. // is smaller than the size of the deque, elements are popped from the end
  351. // until the size is N.
  352. //
  353. define method size-setter (n :: <fixed-integer>, deque :: <deque>)
  354.     => <fixed-integer>;
  355.   let s = size(deque);
  356.   if (n < s)
  357.     for (i from 0 below s - n) pop-last(deque) end for;
  358.   else
  359.     for (i from 0 below n - s) push-last(deque, $deque-fill-default$) end for;
  360.   end if;
  361.   deque.deque-size := n;
  362. end method size-setter;
  363.  
  364. // Since we can traverse from either end, we check to see which end is closer
  365. // to the desired element and take that as our starting point.
  366. //
  367. define method element (deque :: <deque>, key :: <fixed-integer>,
  368.                #key default = no_default) => <object>;
  369.   let sz = deque.size;
  370.   if (key < 0 | key >= sz)
  371.     if (default == no_default) error("No such element in %=: %d", deque, key)
  372.     else default
  373.     end if;
  374.   elseif (key + key > sz)    // closer to end than start
  375.     for (cur_key from sz - 1 above key,
  376.      state = deque.deque-tail then state.prev-deque-element)
  377.     finally state.deque-element-data
  378.     end for;
  379.   else
  380.     for (cur_key from 0 below key,
  381.      state = deque.deque-head then state.next-deque-element)
  382.     finally state.deque-element-data
  383.     end for;
  384.   end if;
  385. end method element;
  386.  
  387. define method element-setter (value, deque :: <deque>, key :: <fixed-integer>)
  388.   let sz = deque.size;
  389.   if (key < 0)
  390.     error("No such element in %=: %d", deque, key)
  391.   elseif (key >= sz)
  392.     size(deque) := key + 1;
  393.   end if;
  394.     
  395.   if (key + key > sz)        // closer to end than start
  396.     for (cur_key from sz - 1 above key,
  397.      state = deque.deque-tail then state.prev-deque-element)
  398.     finally state.deque-element-data := value;
  399.     end for;
  400.   else
  401.     for (cur_key from 0 below key,
  402.      state = deque.deque-head then state.next-deque-element)
  403.     finally state.deque-element-data := value;
  404.     end for;
  405.   end if;
  406. end method element-setter;
  407.  
  408. // map-as -- public
  409. //
  410. // This is done by finding the intersection of the key sequences of the
  411. // collections, and applying the function to each keyed element.  The
  412. // result of this is pushed onto the end of a result deque.  (Everything
  413. // is pushed onto the end so that order will be preserved.)
  414. //
  415. // It is unclear what this should do when you are mapping from tables, so best
  416. // we keep it undefined for now.           -rgs
  417. //
  418. // define method map-as(cls == <deque>, proc :: <function>,
  419. //             collection :: <collection>, #rest more-collections);
  420. //   let result = make(<deque>);
  421. //   let keys = reduce(intersection, key-sequence(collection),
  422. //             map(key-sequence, more-collections));
  423. //   for (key in keys)
  424. //     push-last(result, apply(proc, collection[key],
  425. //                 map(rcurry(element, key), more-collections)));
  426. //   end for;
  427. //   result;
  428. // end map-as;
  429.  
  430. //
  431. // A specialized version of MAP-AS for mapping only sequences into a
  432. // deque.  Iterates using iteration states and CURRENT-ELEMENT instead of
  433. // the key sequences.
  434. //
  435. // Cut down to avoid hassles with iteration protocol across multiple
  436. // collections              -rgs
  437. //
  438. define method map-as (cls == <deque>, proc :: <function>,
  439.               sequence :: <sequence>,
  440.               #next next-method, #rest more-sequences) => <deque>;
  441.   if (empty?(more-sequences))
  442.     let result = make(<deque>);
  443.     for (element in sequence)
  444.       push-last(result, proc(element));
  445.     end for;
  446.     result;
  447.   else 
  448.     next-method();
  449.   end if;
  450. end method map-as;
  451.  
  452. //
  453. // A specialized version of MAP-AS for mapping only deques into a deque.
  454. // Iterates along the structure of the deques rather than using
  455. // CURRENT-ELEMENT as an accessor.
  456. //
  457. // Modified heavily for efficiency.  -- rgs
  458. //
  459. define method map-as (cls == <deque>, proc :: <function>,
  460.              deque :: <deque>, #next next-method, #rest more-deques)
  461.   case
  462.     empty?(more-deques) =>
  463.       let result = make(<deque>);
  464.       for (element = deque-head(deque) then next-deque-element(element),
  465.        while element)
  466.     push-last(result, proc(deque-element-data(element)));
  467.       end for;
  468.       result;
  469.     every?(rcurry(instance?,<deque>), more-deques) =>
  470.       let result = make(<deque>);
  471.       let more-vals = make(<vector>, size: size(more-deques));
  472.       for (element = deque-head(deque) then next-deque-element(element),
  473.        more-elements = map-as(<vector>, deque-head, more-deques)
  474.          then map-into(more-elements, next-deque-element, more-elements),
  475.        while element & every?(identity, more-elements))
  476.     map-into(more-vals, deque-element-data, more-elements);
  477.     push-last(result, apply(proc, deque-element-data(element), more-vals));
  478.       end for;
  479.       result;
  480.     otherwise =>
  481.       next-method();
  482.   end case;
  483. end map-as;
  484.  
  485. define method map-into (destination :: <deque>,
  486.             proc :: <function>, sequence :: <sequence>,
  487.             #next next_method, #rest more_sequences)
  488.   if (empty?(more_sequences))
  489.     for (elem in sequence,
  490.      state = destination.deque-head then state & state.next-deque-element)
  491.       if (state) state.deque-element-data := proc(elem)
  492.       else push-last(destination, proc(elem))
  493.       end if;
  494.     end for;
  495.     destination;
  496.   else
  497.     next_method();
  498.   end if;
  499. end method map-into;
  500.  
  501.  
  502.  
  503. // Sequence Function Methods
  504.  
  505. // More of the sequence functions have been specialized for deques because
  506. // they are improved more than the general collection functions by
  507. // knowledge of the data structure.
  508. //
  509. // Especially useful are the specializations of the mutator functions
  510. // (ones that end in !) which are allowed to change the data structure.
  511. // These can be made very space and time efficient for deques.  However,
  512. // the code for these functions also looks messier because it grunges
  513. // around with the structure of the deque object.
  514. //
  515. // Other functions will usually use either recursive helper functions
  516. // (especially those with funny keys for counting the number of things to
  517. // remove and so forth, because it is easier to deal with things that way)
  518. // or more abstract forms such as for-each.
  519. //
  520. // Some of the sequence functions have been specialized not for
  521. // efficiency, but for order stability.  Since deques are by nature an
  522. // ordered data structure, order should be preserved in deque operations,
  523. // and this cannot be guaranteed in the general sequence methods.
  524.  
  525. // add -- public
  526. //
  527. // Create a new deque with the NEW element added to it.  Add must
  528. // function similarly to add!, so this adds to the front of the
  529. // deque.
  530. //
  531. define method add (deque :: <deque>, new) => <deque>;
  532.   let new-deque = copy-sequence(deque);
  533.   push(new-deque, new);
  534. end method add;
  535.  
  536. // add! -- public
  537. //
  538. // Add a NEW element to a deque destructively.  This is another name
  539. // for push (so it adds to the front of the deque).
  540. //
  541. define method add! (deque :: <deque>, new) => <deque>;
  542.   push(deque, new);
  543. end method add!;
  544.  
  545. // remove -- public
  546. //
  547. // Create a new deque with COUNT copies of element VALUE removed from it.
  548. // If COUNT is not given, remove all copies of VALUE from the new deque.
  549. // The TEST key always the equality test to be specified.
  550. //
  551. // The helper function COPY runs down the deque creating a copy, but
  552. // skipping the element VALUE as long as COUNT does not run out.
  553. //
  554. define method remove (deque :: <deque>, value,
  555.               #key test = \==, count) => <deque>;
  556.   let count = count | size(deque);
  557.   local method copy(state :: union(singleton(#f), <deque-element>),
  558.             count :: <fixed-integer>) => <deque>;
  559.       case
  560.         ~state =>
  561.           make(<deque>);
  562.         count <= 0 | ~test(deque-element-data(state), value) =>
  563.           push(copy(next-deque-element(state), count),
  564.            deque-element-data(state));
  565.         otherwise =>
  566.           copy(next-deque-element(state), count - 1);
  567.       end case;
  568.     end method;
  569.   copy(deque-head(deque), count);
  570. end method remove;
  571.  
  572. // remove! -- public
  573. //
  574. // Remove up to COUNT copies of VALUE from the deque.  If COUNT is not
  575. // given, remove all copies of VALUE.  The deque is destructively
  576. // modified.  The TEST key allows the equality test to be specified.
  577. //
  578. // The helping function SCAN! runs down the deque, DROP!ping elements
  579. // which match VALUE.  When COUNT runs out it quits.
  580. //
  581. define method remove! (deque :: <deque>, value,
  582.                #key test = \==, count: count) => <deque>;
  583.   let count = count | size(deque);
  584.   local method scan!(state :: union(singleton(#f), <deque-element>),
  585.              count :: <fixed-integer>)
  586.       case
  587.         count <= 0 | ~state =>
  588.           #t;
  589.         test(deque-element-data(state), value) =>
  590.           drop!(deque, state);
  591.           scan!(next-deque-element(state), count - 1);
  592.         otherwise =>
  593.           scan!(next-deque-element(state), count);
  594.       end case;
  595.     end method scan!;
  596.   scan!(deque-head(deque), count);
  597.   deque;
  598. end method remove!;
  599.  
  600. // choose -- public
  601. //
  602. // Creates a new deque containing only those elements which satisfy
  603. // PREDICATE.  Uses FOR-EACH to check every element of DEQUE and appends
  604. // those which satisfy to the new RESULT deque.
  605. //
  606. define method choose (predicate :: <function>, deque :: <deque>) => <deque>;
  607.   let result = make(<deque>);
  608.   for (element in deque)
  609.     if (predicate(element)) push-last(result, element) end if;
  610.   end for;
  611.   result;
  612. end method choose;
  613.  
  614. // choose-by -- public
  615. //
  616. // Creates a new deque containing only those elements of VALUE-DEQUE which
  617. // correspond to elements in TEST-SEQUENCE which satisfy PREDICATE.  Uses
  618. // FOR-EACH to check each element of DEQUE and append good ones to RESULT.
  619. //
  620. define method choose-by (predicate :: <function>, test-sequence :: <sequence>,
  621.              value-deque :: <deque>) => <deque>;
  622.   let result = make(<deque>);
  623.   for (test-element in test-sequence,
  624.        value-element in value-deque)
  625.     if (predicate(test-element)) push-last(result, value-element) end if;
  626.   end for;
  627.   result;
  628. end method choose-by;
  629.  
  630. // remove-duplicates -- public
  631. //
  632. // Remove duplicate items from DEQUE.  The test for duplicates may be
  633. // specified by the TEST keyword.
  634. //
  635. // The helper function MEMBER? checks whether a value occurs further down
  636. // the deque from a particular state.  The helper function COPY returns a
  637. // copy of the deque, but whenever it encounters a value that occurs later,
  638. // it is skipped.
  639. //
  640. define method remove-duplicates (deque :: <deque>,
  641.                  #key test = \==) => <deque>;
  642.   local method member?(value, state)
  643.       for (state = state then next-deque-element(state),
  644.            while state & ~test(value, deque-element-data(state)))
  645.       finally
  646.         state;
  647.       end for;
  648.     end method member?,
  649.         method copy(state)
  650.       case
  651.         ~state =>
  652.           make(<deque>);
  653.         member?(deque-element-data(state), next-deque-element(state)) =>
  654.           copy(next-deque-element, state);
  655.         otherwise =>
  656.           push(copy(next-deque-element(state)), deque-element-data(state));
  657.       end case;
  658.     end method copy;
  659.   copy(deque-head(deque));
  660. end method remove-duplicates;
  661.  
  662. // remove-duplicates! -- public
  663. //
  664. // Remove duplicate items from DEQUE.  The test for duplicates may be
  665. // specified by the TEST keyword.  The deque is destructively modified by
  666. // REMOVE-DUPLICATES!.
  667. //
  668. //The helper function MEMBER? checks whether a value occurs further down
  669. // the deque from a particular state.  The helper function SCAN! runs down
  670. // the deque, and whenever it encounters a value that occurs later, it
  671. // drops the element.
  672. //
  673. define method remove-duplicates! (deque :: <deque>,
  674.                   #key test = \==) => <deque>;
  675.   local method member?(value, state)
  676.       for (state = state then next-deque-element(state),
  677.            while state & ~test(value, deque-element-data(state)))
  678.       finally state;
  679.       end for;
  680.     end method member?,
  681.         method scan!(state)
  682.       case
  683.         ~state =>
  684.           #t;
  685.         member?(deque-element-data(state), next-deque-element(state)) =>
  686.           drop!(deque, state);
  687.           scan!(next-deque-element(state));
  688.         otherwise =>
  689.           scan!(next-deque-element(state));
  690.       end case;
  691.     end method scan!;
  692.   scan!(deque-head(deque));
  693.   deque;
  694. end method remove-duplicates!;
  695.  
  696. // copy-sequence -- public
  697. //
  698. // Returns a copy of the deque which shares no structure with the
  699. // original.  The keyword START gives an inclusive beginning to the copy;
  700. // it defaults to 0.  The keyword END gives an exclusive end to the copy;
  701. // it defaults to the length of the deque.
  702. //
  703. // The helper function COPY runs down the deque pushing elements onto a
  704. // copy of the original.  It starts pushing elements at the STARTth
  705. // element and stops before the ENDth element or at the end of the deque.
  706. //
  707. define method copy-sequence (source :: <deque>,
  708.                  #key start: first = 0, end: last) => <deque>;
  709.   let last = last | size(source);
  710.   if (first > last) 
  711.     error("End: (%=) is smaller than start: (%=)", last, first);
  712.   end if;
  713.  
  714.   local method copy(state, first, last)
  715.       case
  716.         ~state =>
  717.           make(<deque>);
  718.         first > 0 =>
  719.           copy(next-deque-element(state), first - 1, last - 1);
  720.         last > 0 =>
  721.           push(copy(next-deque-element(state), first, last - 1),
  722.            deque-element-data(state));
  723.         otherwise =>
  724.           make(<deque>);
  725.       end case;
  726.     end method copy;
  727.   copy(deque-head(source), first, last);
  728. end method copy-sequence;
  729.  
  730. // concatenate-as -- public
  731. //
  732. // A new deque is made, each sequence is taken one at a time, and each
  733. // element of the sequence is pushed onto the end of the new deque.  The
  734. // deque is returned.
  735. //
  736. define method concatenate-as (cls == <deque>, sequence :: <sequence>,
  737.                   #rest more-sequences)
  738.   let result = make(<deque>);
  739.   for (element in sequence) push-last(result, element) end for;
  740.   for (sequence in more-sequences)
  741.     for (element in sequence) push-last(result, element) end for;
  742.   end for;
  743.   result;
  744. end method concatenate-as;
  745.  
  746. // replace-subsequence! -- public
  747. //
  748. // Uses the default method.
  749.  
  750. // reverse -- public
  751. //
  752. // Creates a new deque which is the reversal of DEQUE.  Uses FOR-EACH to
  753. // push each element onto the RESULT deque.  Since PUSH is used, the
  754. // resulting deque is backwards.
  755. //
  756. define method reverse (deque :: <deque>) => <deque>;
  757.   let result = make(<deque>);
  758.   for (element in deque) push(result, element) end for;
  759.   result;
  760. end method reverse;
  761.  
  762. // reverse! -- public
  763. //
  764. // Reverses DEQUE destructively.  Uses a FOR loop to run down the deque.
  765. // Each element's NEXT-DEQUE-ELEMENT and PREV-DEQUE-ELEMENT pointers are
  766. // swapped.  Finally, the DEQUE-HEAD and DEQUE-TAIL of the deque are
  767. // swapped.  This reverses the deque using the original deque elements.
  768. //
  769. define method reverse! (deque :: <deque>) => <deque>;
  770.   for (state = deque-head(deque) then prev-deque-element(state),
  771.        while state)
  772.     let (prev, next) = values(prev-deque-element(state),
  773.                   next-deque-element(state));
  774.     prev-deque-element(state) := next;
  775.     next-deque-element(state) := prev;
  776.   end for;
  777.   let (head, tail) = values(deque-head(deque), deque-tail(deque));
  778.   deque-head(deque) := tail;
  779.   deque-tail(deque) := head;
  780.   deque;
  781. end method reverse!;
  782.  
  783. // last -- public
  784. //
  785. // Returns the last element of the duque.  This is more efficient because
  786. // the last element of a deque can be accessed directly.
  787. //
  788. define method last (deque :: <deque>, #key default = no_default)
  789.   let deque-tail = deque-tail(deque);
  790.   case
  791.     deque-tail =>
  792.       deque-element-data(deque-tail);
  793.     default == no-default =>
  794.       error("No such element in %=:  last.", deque);
  795.     otherwise =>
  796.       default;
  797.   end case;
  798. end method last;
  799.  
  800. // last-setter -- Set last element of deque.
  801. //
  802. // Corresponding efficient implementation for the setter of LAST.
  803. //
  804. define method last-setter(new, deque :: <deque>)
  805.   let deque-tail = deque-tail(deque);
  806.   if (deque-tail)
  807.     deque-element-data(deque-tail) := new;
  808.   else
  809.     error("No such element in %=:  last.", deque);
  810.   end if;
  811. end method last-setter;
  812.  
  813.